Computer graphics systems have been widely used by designers to design objects such as cars, airplanes, tooling, and the like. In recent years, computer graphics systems have been applied to more and more complex jobs. The objects rendered have improved from the early vector displays to photorealistic images.
Computer graphic systems typically employ what is known as primitives to create and display user specified geometric structures. Typical two-dimensional structures are points, lines, circles, and polygons.
Three-dimensional objects often are represented in polyhedral form. Polyhedra, by definition, are three-dimensional solids formed by a set of planar faces or polygons. Curved surfaces of three-dimensional objects are typically approximated by displaying a combination of many small polygons.
Often, designers only want to view a portion of the object. To avoid the rendering problems and clutter inherent in displaying data that is not within the prescribed visible range, graphic systems utilize what is known as a "view clipping" feature. This view clipping feature allows a designer to define a "window" in which a portion of the object is rendered. View clipping is performed using two-dimensional polygon clippers, such as the Sutherland-Hodgman (Sutherland et al., "Reentrant Polygon Clipping", Communications of the ACM 17:32-42 (1974)) and the Weiler-Atherton (Weiler et al., "Hidden Surface Removal Using Polygon Area Sorting", Computer Graphics 11:214-222 (1977)) methods. These two-dimensional clippers clip the two or three dimensional objects against the defined window.
In contrast to view clipping, designers often want to inspect their designs from within. This is typically known as "sectioning." To accomplish this task, some computer graphics systems allow the designer to define arbitrary planes about the objects. Each plane demarcates two infinite half-spaces, an acceptance half-space or region and a rejection half-space or region. The intersection of the planes with themselves and the object produce cut-away views which expose the interior of the object. Sectioning is a powerful tool for the graphics system designer.
However, conventional computer graphics systems have several disadvantages when employing sectioning. The primary drawback with sectioning is that the internal area of the polyhedral representation of a solid object when rendered appears hollow to the designer. The polygonal shell that is used to represent the three-dimensional object becomes apparent when the sectioned areas are no longer drawn. The reason for this is that conventional computer graphics systems use two-dimensional clippers to section three-dimensional objects. Two-dimensional clippers deal properly with closed polygons in three-dimensional space, but lack robustness when dealing with closed polyhedra. After sectioning, three-dimensional objects become a disjoint collection of polygons and their volume-enclosing property is difficult to restore.
To solve this problem, conventional computer graphics systems often employ techniques such as "back face coloring" in conjunction with application of two-dimensional clippers. Back face coloring sets "back face" attributes of a polygon to display a constant fill color while the front faces of the same polygon are shaded normally. When a sectioning plane exposes the interior of an object, the back face fill color becomes visible, thus reducing the hollow appearance of the object.
Back face coloring techniques have several disadvantages and/or limitations. First, back face coloring does not employ lighting calculations and thus cannot render proper shading perspectives. As such, a sectioned object does not appear realistic. Additionally, rendering of the back face polygons can be a time consuming task.
Work done at Brigham Young University (Christiansen et al., "Movie.BYU Training Text", University Press, Brigham Young University, 1983. This reference is incorporated by reference in its entirety herein.) introduced the concept of capping sectioned polyhedra. This work depended on a large database accumulation of the rejected portions of the object. This approach is limited to systems that have access to the entire polyhedral data base at the same time. Given the graphics pipeline, as described in this invention, where only one polygon is available at a time, a new approach had to be found.
Work done at Rensselaer Polytechnic Institute (RPI) (Schmidt, Daniel G., "VIRA, A Visibility Resolving Algorithm for Constructive Solid Geometry Using A-Buffer Techniques", Masters Thesis, Electrical, Computer and Systems Engineering Department, Rensselaer Polytechnic Institute, August 1986. This reference is incorporated by reference in its entirety herein.) introduced a method for capping on the near view clip plane. The RPI work is limited in that it did not include capping sectioned polyhedra.